Exemplary embodiments of the present invention are directed to searching documents. Searching for the occurrence of one or more words can currently be performed within documents using productivity software (e.g., a word processor, spreadsheet editor, presentation software, etc.), across documents using an operating system or computer system-wide searching application, as well as on the internet using a search engine. These search techniques typically require at least the search term(s) comprising the search query to be in plaintext form, and may require both the search term(s) as well as the document(s) being searched to be in plaintext form.
The rise of cloud-based data storage has renewed interest in protocols allowing private searching of encrypted or sensitive data in a public or untrusted environment. These protocols are known as Private Set Intersection (PSI) protocols, which are also referred to as Oblivious Keyword Search, or Private Information Retrieval. These techniques provide a blind search functionality to protect the plaintext of the original query from the database provider.
Many recent approaches to PSI involve protocols with a strict set of security assumptions. For example, many approaches require that the person making the query obtain no information about the provider's database beyond the results of the intersection between the query and the contents of the database. This can involve using an independent third party that restricts the set of legitimate queries to achieve these strict security requirements.